#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int LIS(const vector<int>& a) {
    // dp[i] 储存以a[i]为结尾的最长递增子序列的长度
    vector<int> dp(a.size(), 1); // 初始化为1
    // last[i] 储存以a[i]为结尾的最长递增子序列中，对应上一个数字的下标位置
    vector<int> last(a.size(), -1); // 初始化为-1

    int max_i = 0; // 维护当前储存了最长子序列的位置

    // 动态规划：从第二个数字开始依次完成填表
    for (int i = 1; i < a.size(); i++) {
        // 对于dp[i]，遍历i前面的结果，尝试找到最大的dp[j] + 1 = dp[i]
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) { // 首先判断是否满足递增的要求
                if (dp[j] + 1 > dp[i]) { // 然后判断是否找到更大的结果
                    // 找到更优的结果并更新状态
                    dp[i] = dp[j] + 1;
                    last[i] = j;
                    if (dp[i] > dp[max_i])
                        max_i = i;
                }
            }
        }
    }

    // 填表完毕，输出结果
    // 使用栈进行顺序调整
    stack<int> stack;
    for (int i = max_i; i >= 0; i = last[i]) {
        stack.push(a[i]);
    }
    cout << "最长递增子序列是:";
    while (!stack.empty()) {
        cout << " " << stack.top();
        stack.pop();
    }
    cout << endl;

    // 返回最长递增子序列的长度
    return dp[max_i];
}

int main() {
    vector<int> a = {11, 8, 3, 6, 4, 7, 99, 14};
    int len = LIS(a);
    cout << "最长递增子序列的长度为: " << len << endl;
    return 0;
}